Multimedia database image retrieval techniques are known which attempt to find and retrieve a matching image or matching images from a database of stored multimedia images. Such retrieval techniques are becoming commonplace with the proliferation of information disseminated and available over computer networks such as the Internet. Massive amounts of multimedia data are stored in databases supporting web pages and servers, including text, graphics, video and audio. Searching and finding matching multimedia images can be time and computationally intensive.
Queries employed to find matching images typically compute statistics for the image and compare the statistics to a database of statistics from potential matches. Alternatively, the image is subdivided into regions and statistics computed for each region. The statistics are combined into a vector quantity in a high-dimensional space, and comparison between two images involves computing, for example, the Euclidean distance between the vectors to determine similarity. Vectors which are “near” to each other correspond to images which are similar.
In the case of images, however, typical prior art techniques tend to check every image in the database for similarity, a process which is very slow for large data sets. Indexing techniques such as a K-d tree may be used to augment the search, but frequently fail to effectively restrict the search to a small portion of the database, resulting in an exhaustive “brute force” search methodology, particularly with multidimensional spaces greater than 20 dimensions.
The dimensionality performance issue has been addressed by Locality-Sensitive Hashing (“Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,” in Proc. 30th Symposium on Theory of Computing (1998)). Standard similarity metrics, however, such as Euclidean and Manhattan distance-based algorithms, cannot take full advantage of advantages of multidimensional near-neighbor searching provided by Locality-Sensitive Hashing (LSH) because they do not satisfy certain properties exploited by LSH.
Further, comparison techniques used for images tend to be sensitive to common transformations. Such comparison techniques may not be robust enough to detect a match between two images that differ by a subtle geometric transformation, such as rotation, translation, or scaling.
Accordingly, it would be beneficial to develop an efficient method for finding near-similar images which avoids an exhaustive search of all candidate data and which is resilient to minor geometric transformations of similar images.